{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " Nombres premiers et RSA\n", "
\n", "

Navigation dans la page

\n", "

\n", " Si c'est votre première visite dans ce TP, lisez attentivement chacun des points détaillé après ce paragraphe.
\n", " Si vous avez déjà commencer à travailler sur ce TP et que vous souhaiter vous déplacer rapidement dans une partie précise vous pouvez choisir la partie que vous souhaitez rejoindre ci-dessous.
\n", "

\n", " Menu de navigation\n", " \n", "
\n", "

\n", "\n", "
\n", " Technologie jupyter\n", "

\n", " La technologie jupyter permet d'exécuter du code python par un simple clique sur Executer ci-dessus.
\n", " Les morceaux de code de cette page sont interprétées case par case. Pour savoir quelle case a été interprétée avant une autre, il suffit de repérer le numéro devant la case.
\n", " Une fois qu'une case a été interprétée (=exécutée), la page garde en mémoire les variables et fonctions lues
\n", " La plateforme propose quelques outils de purge de la mémoire : \n", "

\n", "

\n", "
\n", "

SAUVEGARDER VOTRE TRAVAIL

\n", "

\n", " Pour ne pas perdre votre travail pensez à le sauvegarder régulièrement. Par défault, la sauvegarde par un clic sur la disquette en haut à gauche de page, ou par le racourci clavier classique ctrl+S\n", " est une sauvegarde en local, sur le serveur de jupyter. Vous pouvez et devez très régulièrement sauvegarder votre travail sur votre support personnel de sauvegarde (clef USB, se l'envoyer par mail etc). Ce faisant vous disposerez d'un fichier .ipynb (IPYthon NoteBook) qu'il vous suffira de recharger pour avancer. Après le rechargement assurez vous que les fonctionnalités anciennement developpées et variables utilisées sont bien dans la mémoire de la page (en rééxecutant les cases, ou plus rapidement par Kernel > Restart & Run All.

\n", "

A NOTER : vous pouvez travailler sur le tp (et tout autre fichier .ipynb) hors connexion en installant une version local du notebook de jupyter. Il faut que votre machine possède un interpreteur de python et que vous soyez connecter à internet.\n", "

    \n", "
  1. Lancer un terminal
    2. \n", "
  2. Taper la commande suivante : pip install jupyterlab
    3. \n", "
  3. Une fois l'installation terminée portez votre attention sur les dernières lignes affichées dans votre terminal vous invitant probablement à taper une ligne de commande pour faire une mise à jour
    4. \n", "
  4. Pour lancer notebook de jupyter, taper dans votre termial : jupyter notebook
    5. \n", "
  5. Votre simulateur de serveur est lancé. Il ne faut pas fermer votre terminal, auquel cas votre simulateur de serveur s'interompera. Suivez le lien indiqué dans les dernières lignes de votre terminal pour vous diriger vers votre espace local. L'interface se présente comme celle que vous trouverez sur le web. Votre travail sera cependant toujours enregistré et jamais perdu même si vous le consultez après plusieurs jours
    6. \n", "
\n", "

\n", "
\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Comme pour le TP1, TP2 et TP3, une bibliothèque regroupant quelques outils de la cryptologie vous ont été donnée. Chargeons l'intégralité des fonctionnalités qu'elle propose

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from OutilsCrypto import *" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Vous êtes invité à travailler sur la première partie du TP1 pour vous refamiliariser avec les fonctionnalités de cette bibliothèque comme codex, codex, xedoc, paquet, mode2base, Filtre ainsi que les fonctions d'attaque par dictionnaire.

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " Partie 1 : Tests de primalité\n", "
\n", "\n", "

\n", "

\n", " Menu de navigation\n", " \n", "
\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

L'objectif de cette section est de comparer en temps (et implicitement en mémoire) différent alogorithme déterministe de primalité. Exécuter la case suivante, qui donner quelques nombre premier.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "Petit_premier=[2, 13, 557, 1223, 99829, 125017]\n", "Grand_premier=[524287, 2147483647, 987012377731]\n", "Ultra_premier=[2**61-1, 2**89-1]\n", "print(Petit_premier)\n", "print(Grand_premier)\n", "print(Ultra_premier)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Test de base

\n", "

D'après la définition, un nombre est premier si il n'a que deux diviseurs. Ecrire la fonction diviseurs(n) qui retourne la liste des diviseurs de n

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def diviseurs(n) :\n", " return []" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Test

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "N=[1, 2, 12, 25, 12345]\n", "for n in N :\n", " print(\"Diviseurs de\", n, \":\", diviseurs(n))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

En déduire un premier test de primalité qui renvoie True si le nombre est premier et False sinon.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def Primal1(n) :\n", " return True" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Tests

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for n in Petit_premier : \n", " top=time.time()\n", " x=Primal1(n)\n", " temps=round(time.time()-top, 3)\n", " print(\"Test de primalité sur\", n, \":\",x, \"(\", temps, \"s)\" )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Optimisation de la mémoire

\n", "

L'inconvénient de la méthode précédente est qu'elle stocke la liste de diviseur dans une variable. Dans la pratique cela n'est pas nécessaire. Ecrire la fonction Primal2(n) qui renvoie True si le nombre est premier et False sinon, en essayant de diviser n par tous les entiers entre $2$ et $n-1$.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def Primal2(n) :\n", " return True" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Test

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for n in Petit_premier : \n", " top=time.time()\n", " x=Primal2(n)\n", " temps=round(time.time()-top, 3)\n", " print(\"Test de primalité sur\", n, \":\",x, \"(\", temps, \"s)\" )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Optimisation du temps de calcul (I)

\n", "

Comme le montre le dernier test (que vous devriez intérompre, par ce qu'il fini dans longtemps : dans le menu supérieur cliquez sur Kernel puis Interupt), le temps de calcul pour des nombre premier supérieur à $10^6$ explose. Cependant nous avons vu en cours, qu'il n'est pas nécessaire de tester tous les nombre entre $2$ et $n-1$. Il suffit en effet de s'arreter à la partie entière de $\\sqrt{n}$. Ecrire la fonction Primal3(n) qui renvoie True si le nombre est premier et False sinon, en essayant de diviser n par tous les entiers entre $2$ et la partie entière de $\\sqrt{n}$.

\n", "

En python, la racine carré d'un nombre s'obtient par la fonction math.sqrt.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def Primal3(n) :\n", " return True" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Tests

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for n in Petit_premier : \n", " top=time.time()\n", " x=Primal3(n)\n", " temps=round(time.time()-top, 3)\n", " print(\"Test de primalité sur\", n, \":\",x, \"(\", temps, \"s)\" )" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for n in Grand_premier : \n", " top=time.time()\n", " x=Primal3(n)\n", " temps=round(time.time()-top, 3)\n", " print(\"Test de primalité sur\", n, \":\",x, \"(\", temps, \"s)\" )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Optimisation du temps de calcul (II)

\n", "

On peut encore diviser le temps de calcul par au moins 2 puisqu'en effet, seul le nombre 2 est paire. Au lieu de tester la division par tous les nombres entre $2$ et la partie entière $\\sqrt{n}$, il suffit de commencer à $3$ et de tester un nombre sur deux. Ecrire la fonction Primal4(n) prennant en compte cette considération.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def Primal4(n) :\n", " return True" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Tests

\n", "

Si vous avez un peu de temps, amusez-vous à exécuter la troisème case... si vous l'osez !

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for n in Petit_premier : \n", " top=time.time()\n", " x=Primal4(n)\n", " temps=round(time.time()-top, 3)\n", " print(\"Test de primalité sur\", n, \":\",x, \"(\", temps, \"s)\" )" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for n in Grand_premier : \n", " top=time.time()\n", " x=Primal4(n)\n", " temps=round(time.time()-top, 3)\n", " print(\"Test de primalité sur\", n, \":\",x, \"(\", temps, \"s)\" )" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "for n in Ultra_premier : \n", " top=time.time()\n", " x=Primal4(n)\n", " temps=round(time.time()-top, 3)\n", " print(\"Test de primalité sur\", n, \":\",x, \"(\", temps, \"s)\" )" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " Partie 2 : Le crible d'Eratosthène et Riemann\n", "
\n", "\n", "\n", "

\n", "

\n", " Menu de navigation\n", " \n", "
\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Nous avons explorer en TD, le crible d'Eraosthène, qui permet par de simple \"bond\" de se priver de l'opétation % (assez chronophage) et qui donne de plus la liste de tous les nombres premiers inférieur à un nombre donnée.
Ecrire la fonction Erato(n) qui renvoie cette liste (sans appeler les fonctions précédentes).

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def Erato(n) : \n", " return []" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Tests

" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "top=time.time()\n", "era=Erato(1000000)\n", "temps=round(time.time()-top, 3)\n", "print(\"Liste des nombres premiers inférieur à 1 000 000 obtenue en\", temps, \"s : \")\n", "print(era)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

La fonction $\\pi$ de Riemann

\n", "

Comme nous l'avons explorer en cours, il existe un \"pont de compréhension\" entre d'une part l'unvers des études de fonctions (l'analyse) et la cryptographie (l'arithmétique) à travers la fonction $\\zeta$ de Riemann. Il se trouve que cet illustre mathématicien c'est longtemps intéréssé aux nombres premiers et à leur répartition. Avant d'introduire sa célèbre fonction $\\zeta$, il c'est beaucoup intéréssé au nombre de nombre premier plus petit qu'un nombre donnée. Etant donné un entier $n$, il note $\\pi(n)$ le nombre de nombre premier inférieur ou égale à $n$. L'algorithme d'Eratosthène permet de réprésenter très rapidement cette fonction. Bien avant le formalisme de Riemann, Gauss, alors agé de 16 ans, a observer que ce nombre $\\pi(n)$ se rapprochait de $\\dfrac{n}{ln(n)}$ pour $n$ suffisament grand. Depuis il a été démontré que pour $n$ suffisament grand \n", "$$\\dfrac{n}{ln(n)-\\frac{3}{2}}<\\pi(n)<\\dfrac{n}{ln(n)-\\frac{1}{2}}$$\n", "

\n", "

\n", "La fonction FonctionPi(xmin, xmax) trace la focntion $n\\mapsto \\pi(n)$ ainsi que les deux fonctions d'encadrement. En l'utilisant et par observation graphique, détermner le plus petit entier $N$ tel que \n", " $$\\forall n\\geqslant N, \\quad\\dfrac{n}{ln(n)-\\frac{3}{2}}<\\pi(n)<\\dfrac{n}{ln(n)-\\frac{1}{2}}$$\n", "(Il est plus petit que 100)\n", "

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from pylab import *\n", "def FonctionPi(xmin, xmax) :\n", " try : \n", " xmin=int(xmin)\n", " xmax=int(xmax)\n", " except : \n", " xmin=10\n", " xmax=50\n", " if(xmin<=1 or xmax<=xmin) :\n", " xmin=10\n", " xmax=50\n", " \n", " era=Erato(xmax)\n", "\n", " y=[]\n", " y.append(0)\n", " for i in range(1, xmax+1) :\n", " y.append(y[i-1])\n", " if(i in era) : y[i]+=1\n", " plot(range(xmin, xmax+1), y[xmin:], 'r', label=\"$\\pi$ sur $[\"+str(xmin)+\", \"+str(xmax)+\"]$\")\n", " \n", " if(xmin<=1) : xmin=2 \n", " \n", " y1=[]\n", " for i in range(xmin, xmax+1) : y1.append(i/(log(i)-1.5))\n", " plot(range(xmin, xmax+1), y1, 'b', label=\"$n\\mapsto \\dfrac{n}{ln(n)-1,5}$\")\n", " \n", " y2=[]\n", " for i in range(xmin, xmax+1) : y2.append(i/(log(i)-0.5))\n", " plot(range(xmin, xmax+1), y2, 'g', label=\"$n\\mapsto \\dfrac{n}{ln(n)-0,5}$\")\n", " \n", " title(\"Encadrement de $\\pi(n)$ par $\\dfrac{x}{ln(x)-a}$\")\n", " xlim(xmin, xmax)\n", " ylim(0, max([max(y), max(y1), max(y2)]))\n", " legend()\n", " show()" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "FonctionPi(0, 100)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " Partie 3 : Algoritme EMR\n", "
\n", "\n", "\n", "

\n", "

\n", " Menu de navigation\n", " \n", "
\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Ecrire la fonction EMR(x, n, m) permettant, comme détaillé dans le cours, de calculer l'exponentiation modulaire rapide $x^n\\ mod\\ m$.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def EMR(x, n, m) :\n", " return 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Tests

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "X=[12, 345, 6789, 123456789]\n", "N=[123, 4567, 891011, 987654321]\n", "M=[9876, 54321, 123456789,10111213141516171819]\n", "for i in range(4):\n", " print(X[i], \"^\", N[i], \"modulo\", M[i], \"=\", EMR(X[i], N[i], M[i]))\n", "#Résultats attendus : \n", "#996, 41073, 20144106 et 7968005404683189968" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " Partie 4 : RSA\n", "
\n", "\n", "

\n", "

\n", " Menu de navigation\n", " \n", "
\n", "

" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Commençont par déterminer la taille des paquet. On rappel que si $26\\leqslant n<2526$ alors on sera en paquet de 1, si $2526\\leqslant n<252526$ alors on sera en paquet de 2, etc.
Ecrire la fonction taille_paquet(n) qui renvoie la taille du paquetage.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def taille_paquet(n) :\n", " return 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Test

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "N=[25, 26, 2000, 3000, 300000, 5000000000]\n", "for n in N : print(n, \"=>\", taille_paquet(n))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Ecrire la fonction ERSA(txt, clef) qui prend en paramètre un texte claire txt et une clef publique du chiffrement RSA clef qui est un tableau à deux cases (la case 0 est le \"$n$\" et la case 1 est le \"$e$\") et qui renvoie le message chiffré suivant le cryptosystème RSA.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def ERSA(txt, clef) :\n", " return \"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Test

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "n=122090867\n", "e=1223\n", "txt0=\"UNJOURJESERAISLEMEILLEURDRESSEUR\"\n", "txt1=ERSA(txt0, [n,e])\n", "print(txt1)\n", "#Attendu : 86383270-118437731-109277500-82791442-79517390-57128326-29908867-29376781" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Ecrire la fonction DRSA(txt, clef) qui prend en paramètre un texte chiffré suivant le cryptosystème RSA txt et la clef privée de déchiffrement clef qui est un tableau à deux cases (la case 0 est le \"$n$\" et la case 1 est le \"$d$\") et qui renvoie le message claire.

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def DRSA(txt, clef) :\n", " return \"\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Test

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "n=122090867\n", "d=97751447\n", "txt0=\"86383270-118437731-109277500-82791442-79517390-57128326-29908867-29376781\"\n", "txt1=DRSA(txt0, [n,d])\n", "print(txt1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Génération de clef

\n", "

Reprenez les fonctions deu TP2 permettant de calculer le PGCD entre deux nombres et l'inverse modulaire

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def PGCD(a, b) :\n", " return 0" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def inv_mod(a, n) :\n", " return 0" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Ecrire la fonction GenRclef qui renvoie un tableau asociatif a deux champs : \n", "

\n", "correspondant au principe de construction de clef publique, clef privé du cryptosystème RSA.\n", "

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def GenRclef(B=10000) :\n", " res={}\n", " res[\"PUBLIQUE\"] = [0, 0]\n", " res[\"PRIVE\"] = [0, 0]\n", " return res" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "

Test

" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "clef=GenRclef()\n", "txt0=\"MONPETITOISEAUAPRISSAVOLEEMONPETITOISEAUAPRISSAVOLEEAPRISCAALAVOLETTEAPRISCAALAVOLETTEAPRISSAVOLEE\"\n", "txt1=ERSA(txt0, clef[\"PUBLIQUE\"])\n", "txt2=DRSA(txt1, clef[\"PRIVE\"])\n", "print(txt0)\n", "print(txt1)\n", "print(txt2)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.0" } }, "nbformat": 4, "nbformat_minor": 2 }